/* Try Eight Queen Problem with C language.
 * 
 * April 2020 by Stone
 *
 * Idea:
 *      Using a two demensional array to represent the chess board. If one
 *      element is on the queen's path, it is set 1, otherwise, it remains 0.
 *      Once put a queen on the chess board, set the elements on its path 
 *      to 1. Once remove a queen, set the elements on its path back to 0.
 */


#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
#define BOARD_WIDTH 8       //how many cells one line of chess board has
#define QUEEN_NUM 8         //quantity of queens
#define STACK_LEN QUEEN_NUM 
#define QUEEN true          //flag that whether there's a queen
#define NO_QUEEN false

typedef unsigned char bool;
typedef bool Cell;         // cell on chess board

typedef struct {
    int x, y;
} Pos;




/* A simple stack to make codes clear. */
typedef struct {
    Pos list [STACK_LEN];     // the list of data elements
    int top;
} Stack;


bool push(Stack *sk, Pos pos){
    if (sk->top > STACK_LEN){
        printf("reach max stack length");
        return false;
    }

    sk->list[sk->top] = pos;
    sk->top += 1;

    return true;
}


bool pop(Stack *sk){
    if (sk->top == 0){
        printf("stack is empty, nothing to pop.");
        return false;
    }
 
    sk->top -= 1;
    return true;
}


bool is_full(Stack *sk){
    if (sk->top == STACK_LEN -1){
        return true;
    }
    return false;
}


void print_stack(Stack *sk){
    printf("stack: ");
    Pos pos;
    for (int i=0; i < sk->top; i++){
        pos = sk->list[i];
        printf("(%i, %i)", pos.x, pos.y);
    }
    printf("<\n");
}


/* Description:
 *      To find if put a queen here, does it be eatten by the others.
 */
bool is_conflict(Cell board[][BOARD_WIDTH], Pos pos){
    
    // walk crossly, step_y = -1 or 1, step_x = -1, 1
    for (int step_y=-1; step_y <= 1; step_y +=2){
        for (int step_x=-1; step_x <= 1; step_x +=2){
            int x = pos.x;
            int y = pos.y;

            while (x>=0 && y>=0 && x<BOARD_WIDTH && y<BOARD_WIDTH){
                if (board[y][x] == QUEEN){
                    return true;
                }

                x += step_x;
                y += step_y;
           }
        }
    }

    //walk horizontally and vertically
    //when step_y==0, step_x = +1, or -1, when step_x==0, step_y=+1 or -1
    for (int step_x=-1; step_x <= 1; step_x +=2){
        int x = pos.x;
        while (x>=0 && x<BOARD_WIDTH){
            if (board[pos.y][x] == QUEEN){
                return true;
            }
            
            x += step_x;
        }
    }

    for (int step_y=-1; step_y <= 1; step_y +=2){
        int y = pos.y;
        while (y>=0 && y<BOARD_WIDTH){
            if (board[y][pos.x] == QUEEN){
                return true;
            }

            y += step_y;
        }
    }

    return false;
}


bool put_queen(Cell board[][BOARD_WIDTH], Pos pos){
    printf("put queen at:(%i, %i) | ", pos.x, pos.y);  //debug
    if (is_conflict(board, pos)){
        printf("put fail\n");  //debug
        return false;
    }

    board[pos.y][pos.x] = QUEEN;
    printf("put done \n");  //debug
    return true;
}


bool del_queen(Cell board[][BOARD_WIDTH], Pos pos){
    printf("del queen; test conflict: %i\n", is_conflict(board, pos)); // debug
    board[pos.y][pos.x] = NO_QUEEN;
    
    return true;
}

/* Description:
 *      Try to find the chess layout with recursion. If it is time to terminate,
 *      the function will return true, and the returned true will propogate
 *      until exit. If the function fail to find an available position for its
 *      queen, it will return false in order to go back to last layer.
 *
 *      The function should terminate when *sk is full or the position of the queen
 *      at the first layer of recursion reaches the border of the chess board.
 * Parameters:
 *      board: the chess board.
 *      *sk: to store the position of queens.
 *      pos: where to put the first queen.      
 */
bool find_layout(Cell board[][BOARD_WIDTH], Stack *sk, Pos pos){
    printf("depth: %i\n", sk->top);  //debug
    print_stack(sk);

   if (is_full(sk)){
        printf("stack full terminate.\n");
        return true;
    }

    while (true){
        //border checking
        if (pos.x >= BOARD_WIDTH){
            pos.x = 0;
            pos.y += 1;
        }
        if (pos.y >= BOARD_WIDTH){
            if (sk->top == 0){
                // over boundary at thie 0th layer should terminate the trying.
                printf("over boundary terminate.\n");
                return true;
            }
            else {
                return false;
            }
        }
        
        //try to find pos of queens in this layer of recursion
        if (put_queen(board, pos)){
            push(sk, pos);

            //go to next layer of recursion
            if (find_layout(board, sk, pos)){
                find_layout(board, sk, pos);
            }
            else{
                del_queen(board, pos);
                pop(sk);
                pos.x += 1;
            }
        }
        else{
            pos.x += 1;
        }
    }
}


void print_board(Cell board[][BOARD_WIDTH]){
    for (int y=0; y <= BOARD_WIDTH; y++){
        for (int x=0; x <= BOARD_WIDTH; x++){
            if (board[y][x] == QUEEN){
                printf("* ");
            }
            else{
                printf("- ");
            }
        }
        printf("\n");
    }
}


int main(){

   Cell board[BOARD_WIDTH][BOARD_WIDTH] = {NO_QUEEN};
   Pos pos = {3, 3};
   /*
   print_board(board);
   printf("is_conflict: %i \n", is_conflict(board, pos));

   board[pos.x][pos.y] = QUEEN;
   print_board(board);
   printf("is_conflict: %i \n", is_conflict(board, pos));
   */

   pos.x = 0;
   pos.y = 0;
   Stack queens_position = {0};
   find_layout(board, &queens_position, pos);
   print_stack(&queens_position);
   print_board(board);
/*
   for (int y=-2; y<=2; y++){
        for (int x= -2; x<=2; x++){
            Pos p = {pos.x+x, pos.y+y};
            printf("%i ", is_conflict(board, p));
        }
        printf("\n");
   }
*/
   return 0;
}
